package demon1;
import com.sun.source.tree.Tree;

import java.util.*;

public class Mytree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }
    public TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left=B;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //前序遍历
    public void prveOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        prveOrder(root.left);
        prveOrder(root.right);
    }
    public void midOrder(TreeNode root){
        if(root==null){
            return;
        }
        midOrder(root.left);
        System.out.print(root.val+" ");
        midOrder(root.right);
    }
    public void latOrder(TreeNode root){
        if(root==null){
            return;
        }
        midOrder(root.left);
        midOrder(root.right);
        System.out.print(root.val+" ");
    }
    public int size1(TreeNode root){
        if(root==null){
            return 0;
        }
        return size1(root.left)+size1(root.right)+1;
    }
    public int count=0;

    public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left == null && root.right == null) {
            count++;
        }
        size2(root.left);
        size2(root.right);
        return count;
    }
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int lefthight=getHeight(root.left)+1;
        int righthight=getHeight(root.right)+1;

        return Math.max(lefthight,righthight);
    }
    int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int ret= getKLevelNodeCount(root.left,k-1);
        int ret2 =getKLevelNodeCount(root.right,k-1);
        return ret+ret2;
    }
    TreeNode find(TreeNode root, int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if(ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;
    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//
//        //逻辑:每次递归判断子树是否和subroot相同,不相同返回false,相同返回true;时间复杂度为m*n
//
//        if(root==null){
//            return false;
//        }
//        if(isSameTree(root,subRoot)){
//            return true;
//        }
//        if(isSubtree(root.left,subRoot)){
//            return true;
//        }
//        if(isSubtree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(q.val!=p.val){
            return false;
        }
        return isSameTree(q.left,p.left)&&isSameTree(q.right,p.right);
    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=null;
        tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);

        invertTree(root.right);
        return root;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        // int leftH=maxHight(root.left);
        // int rightH=maxHight(root.right);
        // return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);
        return maxHight(root)>=1;
    }
    public int maxHight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH=maxHight(root.left);
        if(leftH<0){
            return -1;
        }
        int rightH=maxHight(root.right);
        if(rightH<0){
            return -1;
        }
        if(Math.abs(leftH-rightH)<=1){
            return Math.max(leftH,rightH)+1;
        }else{
            return -1;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return false;
        }
        return isSymmetric2(root.left,root.right);


    }
    public boolean isSymmetric2(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null&&rightTree!=null||rightTree==null&&leftTree!=null){
            return false;
        }
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetric2(leftTree.left,rightTree.right)&&isSymmetric2(leftTree.right,rightTree.left);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(subRoot==null){
            return true;
        }
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSame(root,subRoot);
    }
    public boolean isSame(TreeNode s,TreeNode t){
        if(s==null&&t==null){
            return true;
        }
        if(s==null&&t!=null||s!=null&&t==null){
            return false;
        }
        if(s.val!=t.val){
            return false;
        }
        return isSame(s.left,t.left)&&isSame(t.right,s.right);

    }
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return ;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    //层序遍历非递归实现,通过队列来实现,说明一下实现原理,队列特点是先进先出,想象上课老师画的二叉树
    //先判断根节点,是否为空.接着将根节点入栈,再判断队列是否为空,如果为空不进入循环,直接返回.不为空
    //进入循环,计算队列有多少元素,再进入循环,将上层元素弹出,并将cur记录下来.首先进来的是根节点,最先弹出
    //的也是根节点,下面找cur的左右子节点,找到后,因为这时队列中只有一个元素,又将它弹出此时size为0.代码后面
    //也有size--,只要队列中又元素,里层循环就要一直进行,也就是要一直进入,弹出.想一下,cur.left和cur.right分别是cur的左右子节点
    //将他们都加入对列中此时B,C都入队列了,然后开始弹出元素B,之后又会将B的左右子树入队,一直循环下去.下面这段代码是将每层的元素放入一个
    //顺序表中,然后,又将顺序表放入顺序表中.


    public List<List<Character>> levelOrder2(TreeNode root){
        List<List<Character>> ret =new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Character>list =new ArrayList<>();
            while(size>0){
                TreeNode cur =queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, char p, char q) {
        if(root==null){
            return null;
        }
        if(root.val==p||root.val==q){
            return root;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else{
            return rightTree;
        }
    }
}


//




//判断是不是完全二叉树















//import java.util.Stack;
//
//class MinStack {
//
//    Stack<Integer> stack;
//    Stack<Integer> minStack;
//
//    public MinStack() {
//        stack = new Stack<>();
//        minStack = new Stack<>();
//    }
//
//    public void push(int val) {
//        stack.push(val);
//        if(minStack.empty()) {
//            minStack.push(val);
//        }else {
//            Integer peekVal = minStack.peek();
//            if(val <= peekVal) {
//                minStack.push(val);
//            }
//        }
//    }
//
//    public void pop() {
//        if(stack.empty()) {
//            return;
//        }
//        int popVal = stack.pop();
//        if(popVal == minStack.peek()) {
//            minStack.pop();
//        }
//    }
//
//    public int top() {
//        if(stack.empty()) {
//            return -1;
//        }
//        return stack.peek();
//    }
//
//
//    //要求：常数时间范围内 获取到栈当中的最小值
//    public int getMin() {
//        if(minStack.empty()) {
//            return -1;
//        }
//        return minStack.peek();
//    }